package 二分查找;

public class test4 {
    public int mySqrt(int x){
        if(x<1) return 0;
        long left = 1,right=x;
        while (left<right){
            long mid = left+(right-left+1)/2;
            if(mid*mid<=x) left=mid;
            else right=mid-1;
        }
        return (int)left;
    }

    public int mySqrt1(int x){
        if(x<1) return 0;
        long left = 1,right=x;
        while (left<right){
            long mid = left+(right-left)/2;
            if(mid*mid<x) left=mid+1;
            else right=mid;
        }
        if(left*left>x) return (int) left-1;
        return (int) left;
    }
}
